package com.learn.algorithm.graph;

import java.util.PriorityQueue;

public class LeetCode1631 {

    public int minimumEffortPath(int[][] heights) {
        int n = heights.length;
        int m = heights[0].length;

        int[][] distance = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                distance[i][j] = Integer.MAX_VALUE;
            }
        }

        // (0, 0) 点到自己的距离为0
        distance[0][0] = 0;
        // 记录每个点是否访问过
        boolean[][] visited = new boolean[n][m];
        // 0 行号
        // 1 列号
        // 2 原点到当前位置的距离
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        heap.add(new int[]{0, 0, 0});
        while (!heap.isEmpty()) {
            int[] record = heap.poll();
            int x = record[0];
            int y = record[1];
            int c = record[2];

            if (visited[x][y]) {
                continue;
            }
            // 找到了终点
            if (x == n - 1 && y == m - 1) {
                return c;
            }
            visited[x][y] = true;
            Move.forEachMove(x, y, n, m, new Move.Moved() {
                @Override
                public void to(int nx, int ny) {
                    if (!visited[nx][ny]) {
                        int nc = Math.max(c, Math.abs(heights[x][y] - heights[nx][ny]));
                        if (nc < distance[nx][ny]) {
                            distance[nx][ny] = nc;
                            heap.add(new int[]{nx, ny, nc});
                        }
                    }
                }
            });
        }
        return -1;
    }

//    static class Move {
//
//        public static int[] move = new int[]{-1, 0, 1, 0, -1};
//
//        public static void forEachMove(int x, int y, int limitX, int limitY, Moved moved) {
//            for (int i = 0; i < 4; i++) {
//                int toX = x + move[i];
//                int toY = y + move[i + 1];
//                if (toX >= 0 && toX < limitX && toY >= 0 && toY < limitY) {
//                    moved.to(x + move[i], y + move[i + 1]);
//                }
//            }
//        }
//
//        interface Moved {
//            void to(int toX, int toY);
//        }
//    }
}
